package com.pointstar.dp.tree;

/**
 * 南软2005T2
 * 递归计算二叉树中所有节点的度
 *
 * @author 朱科睿
 */
public class NodeDegree {

    public static void main(String[] args) {
        BinaryTree third1 = new BinaryTree(4);
        BinaryTree third3 = new BinaryTree(6);
        BinaryTree second2 = new BinaryTree(3);
        second2.setFirstChild(third3);
        BinaryTree second1 = new BinaryTree(2);
        second1.setFirstChild(third1);
        second1.setNextSibling(second2);
        BinaryTree root = new BinaryTree(1);
        root.setFirstChild(second1);

        getDegreeOfNode(root);
        System.out.println(root.toString());
    }

    /**
     * 递归计算二叉树中所有节点的度
     *
     * @param root 二叉树根节点
     */
    private static void getDegreeOfNode(BinaryTree root) {

        if (root != null) {
            if (root.firstChild != null) {
                root.degree++;
                BinaryTree currentNode = root.firstChild;
                while (currentNode.nextSibling != null) {
                    root.degree++;
                    currentNode = currentNode.nextSibling;
                }
                getDegreeOfNode(root.firstChild);
            }
            getDegreeOfNode(root.nextSibling);
        }
    }

    /**
     * 二叉树
     */
    static class BinaryTree {
        private int data;
        private int degree;
        BinaryTree firstChild;
        BinaryTree nextSibling;

        public BinaryTree() {
        }

        public BinaryTree(int data) {
            this.data = data;
        }

        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public int getDegree() {
            return degree;
        }

        public void setDegree(int degree) {
            this.degree = degree;
        }

        public BinaryTree getFirstChild() {
            return firstChild;
        }

        public void setFirstChild(BinaryTree firstChild) {
            this.firstChild = firstChild;
        }

        public BinaryTree getNextSibling() {
            return nextSibling;
        }

        public void setNextSibling(BinaryTree nextSibling) {
            this.nextSibling = nextSibling;
        }

        @Override
        public String toString() {
            return "BinaryTree{" +
                    "data=" + data +
                    ", degree=" + degree +
                    ", firstChild=" + firstChild +
                    ", nextSibling=" + nextSibling +
                    '}';
        }

    }

}
